package com.wengu.algorithm.alg;

import com.wengu.algorithm.dto.TaskAlg;
import com.wengu.algorithm.dto.UserAlg;
import com.wengu.algorithm.entity.AssignmentOutcome;
import com.wengu.algorithm.service.AssignmentOutcomeUserService;
import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Collectors;

/**
 * B-ETDA算法实现
 * 结合合作蚁群搜索和基于执行成本权重任务密度的算法
 */
@Slf4j
public class BETDA extends ETDA {


    // 全局信息素矩阵
    private Map<Long, Map<Long, Double>> globalPheromoneMatrix;
    // 局部信息素矩阵
    private Map<Long, Map<Long, Double>> localPheromoneMatrix;



    /**
     * 默认构造函数
     */
    public BETDA() {
        this(9.0, 1, 10, 5, 0.1, 1.0, 2.0, 0.1, 0.9);
    }

    /**
     * 带参数的构造函数
     * @param sigma 高斯核函数的sigma参数
     * @param alpha 权重调节参数
     * @param antCount 蚂蚁数量
     * @param roundCount 迭代轮数
     * @param initialPheromone 初始信息素值
     * @param pheromoneWeight 信息素权重
     * @param heuristicWeight 启发式权重
     * @param evaporationRate 信息素挥发率
     * @param bestSelectionProbability 最优路径选择概率
     */
    public BETDA(double sigma, double alpha, int antCount, int roundCount,
                 double initialPheromone, double pheromoneWeight,
                 double heuristicWeight, double evaporationRate,
                 double bestSelectionProbability) {
        super(sigma, alpha);
        this.antCount = antCount;
        this.roundCount = roundCount;
        this.initialPheromone = initialPheromone;
        this.pheromoneWeight = pheromoneWeight;
        this.heuristicWeight = heuristicWeight;
        this.evaporationRate = evaporationRate;
        this.bestSelectionProbability = bestSelectionProbability;
    }
    /**
     * 带参数的构造函数
     * @param sigma 高斯核函数的sigma参数
     * @param alpha 权重调节参数
     * @param antCount 蚂蚁数量
     * @param roundCount 迭代轮数
     * @param initialPheromone 初始信息素值
     * @param pheromoneWeight 信息素权重
     * @param heuristicWeight 启发式权重
     * @param evaporationRate 信息素挥发率
     * @param bestSelectionProbability 最优路径选择概率
     */
    public BETDA(double sigma, double alpha,double gamma, int antCount, int roundCount,
                 double initialPheromone, double pheromoneWeight,
                 double heuristicWeight, double evaporationRate,
                 double bestSelectionProbability) {
        super(sigma, alpha);
        this.gamma = gamma;
        this.antCount = antCount;
        this.roundCount = roundCount;
        this.initialPheromone = initialPheromone;
        this.pheromoneWeight = pheromoneWeight;
        this.heuristicWeight = heuristicWeight;
        this.evaporationRate = evaporationRate;
        this.bestSelectionProbability = bestSelectionProbability;
    }

    // 定义结果类（如果还没有）
    @Data
    public static class AntPathResult {
        List<TaskAlg> path;
        double utility;
        ConcurrentHashMap<Long, ConcurrentHashMap<Long, Double>> localPheromoneMatrix = new ConcurrentHashMap<>();
        public AntPathResult(){

        }
        public AntPathResult(List<TaskAlg> path, double utility) {
            this.path = path;
            this.utility = utility;
        }
    }

    public List<TaskAlg> allocateTasks(UserAlg user, List<TaskAlg> allTasks,
                                       AssignmentOutcome assignmentOutcome,
                                       AssignmentOutcomeUserService assignmentOutcomeUserService,
                                       Map<Long, TaskAlg> taskCacheMap,
                                       String algName, Set<Long> notIncreaseTaskIdSet, ETDA etda) {
        this.currentUser = user;

        // 初始化信息素矩阵
        initializePheromoneMatrix(allTasks);
        // 存储所有蚂蚁的路径上的任务的参数，包含执行次数和效用值
//        Map<String,Map<Long, TaskAlg>> antPathTaskParams = new HashMap<>();
        // 存储所有蚂蚁的路径
        List<List<TaskAlg>> allAntPaths = new ArrayList<>();
        List<Double> allAntPathUtilities = new ArrayList<>();
        Set<String> antPathSet = new HashSet<>();
        // 初始化空间索引
        spatialIndex = new SpatialIndex(allTasks, sigma);

        // 执行多轮迭代
        for (int round = 0; round < roundCount; round++) {
            // 每轮开始时，局部信息素更新为全局信息素。因为每个任务只能执行一次，所以每只蚂蚁的每个边只能爬一次，所以不需要更新局部信息素，而且要求单轮次的各个蚂蚁互相独立，互不影响
            copyGlobalToLocalPheromone();
            // 存储Future对象的列表
//            List<Future<AntPathResult>> futures = new ArrayList<>();
            // 每只蚂蚁构建路径
            for (int ant = 0; ant < antCount; ant++) {
                List<TaskAlg> antPath = constructAntPath(user, allTasks, taskCacheMap, notIncreaseTaskIdSet);
                String fingerprint = generatePathFingerprint(antPath);
                if ("empty".equals(fingerprint)) {
                    continue;
                }
                if (antPathSet.contains(fingerprint)) {
                    continue;
                }
                // 如果之前没有保存过，则保存路径，并计算效用值。如果指纹一样，则效用值肯定一样
                antPathSet.add(fingerprint);
                // 存储路径，并计算效用值
                allAntPaths.add(antPath);
                // 计算用户总效用值
                double userTotalDeltaF = calculateTotalDeltaF(antPath);
                allAntPathUtilities.add(userTotalDeltaF);
//                Future<AntPathResult> future = executor.submit(() -> {
////                    AntPathResult antPathResult = constructAntPath(user, allTasks, taskCacheMap, notIncreaseTaskIdSet);
//
////                    double pathUtility = calculateTotalDeltaF(antPath);
//                    return new AntPathResult(antPath, 0);
//                });
//                futures.add(future);
            }

            // 收集所有结果
//            for (Future<AntPathResult> future : futures) {
//                try {
//                    AntPathResult result = future.get(); // 阻塞获取结果
//                    allAntPaths.add(result.path);
////                    allAntPathUtilities.add(result.utility);
//                } catch (InterruptedException | ExecutionException e) {
//                    // 处理异常，可以选择记录日志或抛出运行时异常
//                    Thread.currentThread().interrupt(); // 重置中断状态
//                    throw new RuntimeException("蚂蚁路径构建失败", e);
//                }
//            }

            // 更新全局信息素（精英策略 + 挥发机制 + 重复路径增强奖励），并将所有路径进行去重
            updateGlobalPheromone(allAntPaths, allAntPathUtilities);
        }

        // 选择最优路径
        List<TaskAlg> bestPathB = selectBestPath(allAntPaths, allAntPathUtilities);

        // 计算用户总效用值
        double userTotalDeltaFB = calculateTotalDeltaF(bestPathB);


        // 使用ETDA算法进行分配任务，比较哪个效果更好，则使用哪一个
        List<TaskAlg> pathETDA = etda.getBestPath(user, allTasks, taskCacheMap, notIncreaseTaskIdSet);
        double userTotalDeltaFETDA = calculateTotalDeltaF(pathETDA);

        List<TaskAlg> realBestPath = new ArrayList<>();
        double realDeltaF = 0.0;
        if(userTotalDeltaFB > userTotalDeltaFETDA){
            realBestPath.addAll(bestPathB);
            realDeltaF = userTotalDeltaFB;
            user.algName = "BETDA";
        } else if (userTotalDeltaFB == userTotalDeltaFETDA) {
            realBestPath.addAll(bestPathB);
            realDeltaF = userTotalDeltaFB;
            user.algName = "same";
        } else {
            realBestPath.addAll(pathETDA);
            realDeltaF = userTotalDeltaFETDA;
            user.algName = "ETDA";
        }

        user.realPath = realBestPath;
        user.realDeltaF = realDeltaF;
        user.pathB = bestPathB;
        user.pathETDA = pathETDA;
        user.deltaFB = userTotalDeltaFB;
        user.deltaFETDA = userTotalDeltaFETDA;

        // 更新任务执行次数和用户成本
        updateTaskAndUserStatus(user, realBestPath, taskCacheMap, notIncreaseTaskIdSet);

        // 保存用户执行结果
        assignmentOutcomeUserService.saveOutcomeUser(user, assignmentOutcome);
        log.info("用户[{}]执行平台安排的任务后的质量增量总和为[{}]",user.id,realDeltaF);
        return realBestPath;
    }

    /**
     * 初始化信息素矩阵
     * 只需要全局信息素，因为每个任务只能执行一次，所以每只蚂蚁的每个边只能爬一次，所以不需要更新局部信息素，而且要求单轮次的各个蚂蚁互相独立，互不影响
     * @param tasks 所有任务列表
     */
    private void initializePheromoneMatrix(List<TaskAlg> tasks) {
        globalPheromoneMatrix = new HashMap<>();
        localPheromoneMatrix = new HashMap<>();

        // 初始化所有任务间的信息素
        for (TaskAlg task1 : tasks) {
            Map<Long, Double> row1 = new HashMap<>();
            Map<Long, Double> row2 = new HashMap<>();

            for (TaskAlg task2 : tasks) {
                if (!task1.equals(task2)) {
                    row1.put(task2.id, initialPheromone);
                    row2.put(task2.id, initialPheromone);
                }
            }

            globalPheromoneMatrix.put(task1.id, row1);
            localPheromoneMatrix.put(task1.id, row2);
        }
        // 初始化起始点到所有任务的信息素
        Map<Long, Double> row1 = new HashMap<>();
        Map<Long, Double> row2 = new HashMap<>();
        for (TaskAlg task2 : tasks) {
            row1.put(task2.id, initialPheromone);
            row2.put(task2.id, initialPheromone);
        }
        globalPheromoneMatrix.put(0L, row1);
        localPheromoneMatrix.put(0L, row2);
    }

    /**
     * 将全局信息素复制到局部信息素
     */
    private void copyGlobalToLocalPheromone() {
        // 使用 ConcurrentHashMap 替代 HashMap
        localPheromoneMatrix = new ConcurrentHashMap<>();

        // 遍历全局信息素矩阵，复制到本地（线程安全）
        globalPheromoneMatrix.forEach((fromTaskId, row) -> {
            // 使用 ConcurrentHashMap 存储每一行
            ConcurrentHashMap<Long, Double> newRow = new ConcurrentHashMap<>(row);
            localPheromoneMatrix.put(fromTaskId, newRow);
        });
    }

    /**
     * 蚂蚁构建路径
     *
     * @param user                 用户信息
     * @param allTasks             所有任务
     * @param taskCacheMap         任务缓存
     * @param notIncreaseTaskIdSet 不增加质量的任务ID集合
     * @return 蚂蚁构建的路径
     */
    private List<TaskAlg> constructAntPath(UserAlg user, List<TaskAlg> allTasks,
                                           Map<Long, TaskAlg> taskCacheMap,
                                           Set<Long> notIncreaseTaskIdSet) {
//        ConcurrentHashMap<Long, ConcurrentHashMap<Long, Double>> localPheromoneMatrix = new ConcurrentHashMap<>();
        // 拷贝一份新的任务列表，避免修改原始数据
        Map<Long,TaskAlg> candidateTaskMap = new HashMap<>();
        List<TaskAlg> antPath = new ArrayList<>();
        Set<Long> selectedTaskIdSet = new HashSet<>();
        double usedCost = 0;
        double tailX = user.startX;
        double tailY = user.startY;
        Long lastTaskId = null;


        List<TaskAlg> candidateTasks = allTasks.stream().map(item -> {
            TaskAlg task = new TaskAlg();
            task.id = item.id;
            task.taskX = item.taskX;
            task.taskY = item.taskY;
            task.arrivalTime = item.arrivalTime;
            task.duration = item.duration;
            task.endTime = item.endTime;
            task.executionCost = item.executionCost;
            task.distanceCost = item.distanceCost;
            task.totalF = item.totalF;
            task.successProb = item.successProb;
            task.deltaF = item.deltaF;
            task.k = item.k;
            task.fCache = item.fCache;
            candidateTaskMap.put(task.id, task);
            return task;
        }).collect(Collectors.toList());

        if (candidateTasks.isEmpty()) {
            return antPath;
        }

        while (true) {
            TaskAlg nextTask = selectNextTask(antPath, candidateTasks, selectedTaskIdSet,
                    notIncreaseTaskIdSet, tailX, tailY,
                    lastTaskId, user, usedCost,taskCacheMap,candidateTaskMap);

            if (nextTask == null) {
                break;
            }

            // 计算添加该任务的成本
            double distanceCost;
            if (antPath.isEmpty()) {
                distanceCost = calculateDistance(user.startX, user.startY,
                        nextTask.taskX, nextTask.taskY);
            } else {
                distanceCost = calculateDistance(tailX, tailY,
                        nextTask.taskX, nextTask.taskY);
            }

            double totalCost = distanceCost + nextTask.executionCost;

            // 检查预算约束
            if (usedCost + totalCost + calculateFinalTrip(nextTask, user) > user.budget) {
                break;
            }

            // 放入缓存
            taskCacheMap.put(nextTask.id, nextTask);
            // 更新路径和状态
            antPath.add(nextTask);
            selectedTaskIdSet.add(nextTask.id);
            candidateTasks.remove(nextTask);
            usedCost += totalCost;
            tailX = nextTask.taskX;
            tailY = nextTask.taskY;
            // 更新局部信息素
            if (lastTaskId != null) {
                updateLocalPheromone(lastTaskId, nextTask.id);
            } else {
                // 如果上一个任务ID为空，则上一个位置应该为用户的起始点
                updateLocalPheromone(0L, nextTask.id);
            }
            lastTaskId = nextTask.id;
        }

        return antPath;
    }

    /**
     * 选择下一个任务
     */
    private TaskAlg selectNextTask(List<TaskAlg> currentPath, List<TaskAlg> candidateTasks,
                                   Set<Long> selectedTaskIdSet, Set<Long> notIncreaseTaskIdSet,
                                   double tailX, double tailY, Long lastTaskId,
                                   UserAlg user, double usedCost, Map<Long, TaskAlg> taskCacheMap, Map<Long, TaskAlg> candidateTaskMap) {
        if (candidateTasks.isEmpty()) {
            return null;
        }
        Map<Long, Double> preferences = new HashMap<>();
        for (TaskAlg task : candidateTasks) {
            if (selectedTaskIdSet.contains(task.id) || notIncreaseTaskIdSet.contains(task.id)) {
                continue;
            }
            double deltaF = task.calDeltaFCommon();
            if (deltaF <= 0) {
                continue;
            }
            TaskAlg taskCache = taskCacheMap.get(task.id);
            if (taskCache != null && taskCache.k > 0) {
                task.k = taskCache.k;
            } else {
                taskCache = task;
                taskCacheMap.put(task.id, taskCache);
            }
            // 计算旅行成本
            double distanceCost;
            if (currentPath.isEmpty()) {
                distanceCost = calculateDistance(user.startX, user.startY,
                        task.taskX, task.taskY);
            } else {
                distanceCost = calculateDistance(tailX, tailY,
                        task.taskX, task.taskY);
            }

            double totalCost = distanceCost + task.executionCost;
            double weightCost = distanceCost + task.executionCost * alpha;

            // 检查预算约束，如果超出预算，则不考虑该任务
            if (usedCost + totalCost + calculateFinalTrip(task, user) > user.budget) {
                continue;
            }

            // 计算偏好值
            double preference = calculatePreference(lastTaskId, task, candidateTasks,
                    selectedTaskIdSet, notIncreaseTaskIdSet,
                    weightCost, candidateTaskMap, currentPath);
            preferences.put(task.getId(), preference);
        }

        if (preferences.isEmpty()) {
            return null;
        }

        // 按偏好值排序
        List<Map.Entry<Long, Double>> sorted = new ArrayList<>(preferences.entrySet());
        sorted.sort((e1, e2) -> Double.compare(e2.getValue(), e1.getValue()));

        // 按概率选择任务
        if (Math.random() < bestSelectionProbability) {
            // 选择偏好值最高的任务
            return candidateTaskMap.get(sorted.get(0).getKey());
        } else {
            // 按偏好值比例选择其他任务
            double totalPreference = sorted.stream().mapToDouble(Map.Entry::getValue).sum();
            double randomValue = Math.random() * totalPreference;
            double cumulative = 0;

            for (Map.Entry<Long, Double> entry : sorted) {
                cumulative += entry.getValue();
                if (cumulative >= randomValue) {
                    return candidateTaskMap.get(entry.getKey());
                }
            }
            // 默认返回第一个
            return candidateTaskMap.get(sorted.get(0).getKey());

        }

    }

    /**
     * 计算偏好值
     */
    private double calculatePreference(Long lastTaskId, TaskAlg candidate,
                                       List<TaskAlg> allTasks,
                                       Set<Long> selectedTaskIdSet,
                                       Set<Long> notIncreaseTaskIdSet,
                                       double weightCost, Map<Long, TaskAlg> candidateTaskMap, List<TaskAlg> currentPath) {

        // 计算信息素部分
        double pheromonePart = initialPheromone;
        if (lastTaskId != null) {
            Double pheromone = localPheromoneMatrix.get(lastTaskId).get(candidate.id);
            pheromonePart = Math.pow(pheromone != null ? pheromone : initialPheromone, pheromoneWeight);
        } else {
            // 如果是第一个任务，则计算用户起点到第一个任务的路径信息素
            Double pheromone = localPheromoneMatrix.get(0L).get(candidate.id);
            pheromonePart = Math.pow(pheromone != null ? pheromone : initialPheromone, pheromoneWeight);
        }

        // 使用ETDA的calculateUtility方法计算启发式部分
        double heuristicUtility = super.calculateUtility(
                candidate,
                allTasks,
                weightCost,
                selectedTaskIdSet,
                notIncreaseTaskIdSet,
                candidate.calDeltaFCommon(), currentUser.budget, currentUser.usedCost);

        double heuristicPart = Math.pow(heuristicUtility, heuristicWeight);
        return pheromonePart * heuristicPart;
    }



    /**
     * 更新局部信息素
     */
    private void updateLocalPheromone(Long fromTaskId, Long toTaskId) {
        Map<Long, Double> row = localPheromoneMatrix.get(fromTaskId);
        if (row != null) {
            Double currentPheromone = row.get(toTaskId);
            if (currentPheromone != null) {
                // 信息素挥发
                row.put(toTaskId, (1 - evaporationRate) * currentPheromone + evaporationRate * initialPheromone);
            }
        }
    }

    // 锁池：存储每个 (fromTaskId, toTaskId) 对应的锁
    private final ConcurrentHashMap<LockKey, ReentrantLock> lockPool = new ConcurrentHashMap<>();

    // 锁的Key，基于 fromTaskId 和 toTaskId
    private static class LockKey {
        final long fromTaskId;
        final long toTaskId;

        LockKey(long fromTaskId, long toTaskId) {
            this.fromTaskId = fromTaskId;
            this.toTaskId = toTaskId;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            LockKey lockKey = (LockKey) o;
            return fromTaskId == lockKey.fromTaskId && toTaskId == lockKey.toTaskId;
        }

        @Override
        public int hashCode() {
            return Long.hashCode(fromTaskId) * 31 + Long.hashCode(toTaskId);
        }
    }


    /**
     * 更新局部信息素（最小粒度锁）
     */
    private void updateLocalPheromone2(Long fromTaskId, Long toTaskId) {
        // 计算锁Key
        LockKey lockKey = new LockKey(fromTaskId, toTaskId);

        // 获取或创建锁（线程安全）
        ReentrantLock lock = lockPool.computeIfAbsent(lockKey, k -> new ReentrantLock());

        // 加锁（仅针对当前 (fromTaskId, toTaskId) 对）
        lock.lock();
        try {
            Map<Long, Double> row = localPheromoneMatrix.get(fromTaskId);
            if (row != null) {
                Double currentPheromone = row.get(toTaskId);
                if (currentPheromone != null) {
                    // 信息素挥发
                    row.put(toTaskId, (1 - evaporationRate) * currentPheromone + evaporationRate * initialPheromone);
                }
            }
        } finally {
            lock.unlock();
        }
    }

    /**
     * 更新全局信息素V1，可能进入局部最优，allAntPaths里面可能会有重复的路径，也未考虑信息素挥发效应
     */
    private void updateGlobalPheromone(List<List<TaskAlg>> allAntPaths, List<Double> allAntPathUtilities) {
        // 找到最优的两条路径
        List<Integer> bestIndices = findBestPathIndices(allAntPathUtilities, 2);
        List<TaskAlg> bestPath = null;
        if (bestIndices.size() >= 1) {
            // 更新最优路径的信息素
            bestPath = allAntPaths.get(bestIndices.get(0));
            updatePathPheromone(bestPath, initialPheromone);

            if (bestIndices.size() >= 2) {
                // 更新次优路径的信息素
                List<TaskAlg> secondBestPath = allAntPaths.get(bestIndices.get(1));
                updatePathPheromone(secondBestPath, initialPheromone / 2);
            }
        }
        // 清除不需要的路径，只保留最优的两个路径
        allAntPaths.clear();
        allAntPathUtilities.clear();
        if (bestPath != null) {
            allAntPaths.add(bestPath);
            allAntPathUtilities.add(calculateTotalDeltaF(bestPath));
        }
    }

    /**
     * 更新全局信息素（精英策略 + 挥发机制 + 重复路径增强奖励），并更新全路径列表，去重
     */
    private void updateGlobalPheromoneV2(List<List<TaskAlg>> allAntPaths, List<Double> allAntPathUtilities) {
        // 使用Map按指纹分组，保留每个路径的最高效用值
        Map<String, PathWithUtility> pathMap = new HashMap<>();
        // 2. 统计路径出现次数
        Map<String, Integer> pathCountMap = countPathOccurrences(allAntPaths);

        // 3. 找到最优的两条路径（考虑路径重复）
        List<PathWithUtility> bestPaths = findBestPathsWithRepeatCount(allAntPaths, allAntPathUtilities, pathCountMap, 2,pathMap);

        if (!bestPaths.isEmpty()) {
            // 更新最优路径的信息素（重复次数越多，奖励越强）
            PathWithUtility bestPathInfo = bestPaths.get(0);
            double bestPathDelta = calculateAdjustedDelta(initialPheromone, bestPathInfo.repeatCount, bestPathInfo.utility);
            updatePathPheromone(bestPathInfo.path, bestPathDelta);
            log.debug("最优路径奖励: 重复次数={}, 基础奖励={}, 实际奖励={}",
                    bestPathInfo.repeatCount, initialPheromone, bestPathDelta);

            if (bestPaths.size() >= 2) {
                // 更新次优路径的信息素
                PathWithUtility secondBestPathInfo = bestPaths.get(1);
                double secondBestDelta = calculateAdjustedDelta(initialPheromone / 2, secondBestPathInfo.repeatCount, secondBestPathInfo.utility);
                updatePathPheromone(secondBestPathInfo.path, secondBestDelta);
                log.debug("次优路径奖励: 重复次数={}, 基础奖励={}, 实际奖励={}",
                        secondBestPathInfo.repeatCount, initialPheromone / 2, secondBestDelta);
            }
        }
        // 进行一次挥发信息素的操作
        globalPheromoneMatrix.forEach((id,row) -> {
            row.forEach((toTaskId, currentPheromone) -> {
                row.put(toTaskId, (1 - evaporationRate) * currentPheromone + evaporationRate * initialPheromone);
            });
        });
    }


    /**
     * 寻找最优路径（包含重复次数信息）
     */
    private List<PathWithUtility> findBestPathsWithRepeatCount(List<List<TaskAlg>> allAntPaths,
                                                               List<Double> allAntPathUtilities,
                                                               Map<String, Integer> pathCountMap,
                                                               int topN, Map<String, PathWithUtility> pathMap) {


        for (int i = 0; i < allAntPaths.size(); i++) {
            List<TaskAlg> path = allAntPaths.get(i);
            double utility = calculateTotalDeltaF(path);
//            allAntPathUtilities.add(utility);
//            double utility = allAntPathUtilities.get(i);
            String fingerprint = generatePathFingerprint(path);
            if ("empty".equals(fingerprint)) {
                // 忽略空路径，理论上不应该出现
                continue;
            }
            int repeatCount = pathCountMap.get(fingerprint);

            // 如果路径已存在，保留效用值更高的那个
            if (!pathMap.containsKey(fingerprint) || pathMap.get(fingerprint).utility < utility) {
                pathMap.put(fingerprint, new PathWithUtility(path, utility, repeatCount));
            }
        }

        // 按效用值降序排序，返回前topN个
        List<PathWithUtility> uniList = pathMap.values().stream()
                .sorted((p1, p2) -> Double.compare(p2.utility, p1.utility))
                .collect(Collectors.toList());
        // 更新全路径列表，去重并按照效用值降序排序
        allAntPaths.clear();
        allAntPathUtilities.clear();
        for (PathWithUtility pathWithUtility : uniList) {
            allAntPaths.add(pathWithUtility.getPath());
            allAntPathUtilities.add(pathWithUtility.getUtility());
        }
        return uniList.stream().limit(topN).collect(Collectors.toList());
    }

    /**
     * 计算调整后的信息素沉积量（重复路径获得更多奖励）
     */
    private double calculateAdjustedDelta(double baseDelta, int repeatCount, double pathUtility) {
        // 重复路径应该获得更多奖励，因为说明这是共识性的好路径

        if (repeatCount <= 1) {
            return baseDelta; // 唯一路径，基础奖励
        } else {
            // 方案A1: 对数增长（稳定增长）
            double maxRewardMultiplier = 3.0; // 最大奖励倍数
            double rewardMultiplier = Math.min(1.0 + Math.log(repeatCount), maxRewardMultiplier);

            // 方案A2: 线性增长（更激进）
            // double rewardMultiplier = Math.min(1.0 + (repeatCount - 1) * 0.5, 3.0);

            // 方案A3: 结合路径质量（推荐）
//            double qualityFactor = calculatePathQualityFactor(pathUtility);
//            double finalMultiplier = rewardMultiplier * qualityFactor;

            return baseDelta * Math.min(rewardMultiplier, 5.0); // 设置上限避免过度累积
        }
    }

    /**
     * 计算路径质量因子（高质量路径获得额外奖励）
     */
    private double calculatePathQualityFactor(double pathUtility) {
        // 根据路径效用值调整奖励倍数
        if (pathUtility > 0.8) {
            return 1.2; // 高质量路径额外奖励20%
        } else if (pathUtility > 0.5) {
            return 1.1; // 中等质量路径额外奖励10%
        } else if (pathUtility > 0.3) {
            return 1.0; // 一般质量路径基础奖励
        } else {
            return 0.8; // 低质量路径减少奖励（避免奖励差路径）
        }
    }

    /**
     * 统计路径出现次数
     */
    private Map<String, Integer> countPathOccurrences(List<List<TaskAlg>> allAntPaths) {
        Map<String, Integer> pathCountMap = new HashMap<>();
        for (List<TaskAlg> path : allAntPaths) {
            String fingerprint = generatePathFingerprint(path);
            pathCountMap.put(fingerprint, pathCountMap.getOrDefault(fingerprint, 0) + 1);
        }
        return pathCountMap;
    }

    /**
     * 生成路径指纹
     */
    private String generatePathFingerprint(List<TaskAlg> path) {
        if (path.isEmpty()) {
            return "empty";
        }
        return path.stream()
                .map(task -> String.valueOf(task.id))
                .collect(Collectors.joining("-"));
    }

    /**
     * 找到最优路径的索引
     */
    private List<Integer> findBestPathIndices(List<Double> utilities, int count) {
        List<Integer> indices = new ArrayList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingDouble(i -> utilities.get(i)));

        for (int i = 0; i < utilities.size(); i++) {
            pq.offer(i);
            if (pq.size() > count) {
                pq.poll();
            }
        }

        while (!pq.isEmpty()) {
            indices.add(pq.poll());
        }

        Collections.reverse(indices);
        return indices;
    }

    /**
     * 更新路径信息素，更新全局信息素时，考虑挥发作用，在下一轮蚂蚁爬行时，不再重复计算信息素的挥发
     */
    private void updatePathPheromone(List<TaskAlg> path, double delta) {
        if (path.isEmpty()) {
            return;
        }
        // 首个任务的前一个位置应该是用户的起点，默认设置id=0L
        Long prevTaskId = 0L;
        for (int i = 0; i < path.size(); i++) {
            Long currentTaskId = path.get(i).id;
            Map<Long, Double> row = globalPheromoneMatrix.get(prevTaskId);
            if (row != null) {
                Double currentPheromone = row.get(currentTaskId);
                if (currentPheromone != null) {
                    double totalPheromone = currentPheromone + delta;
                    row.put(currentTaskId, totalPheromone);
                }
            }

            prevTaskId = currentTaskId;
        }
    }

    /**
     * 选择最优路径
     */
    private List<TaskAlg> selectBestPath(List<List<TaskAlg>> allAntPaths, List<Double> allAntPathUtilities) {
        if (allAntPaths.isEmpty()) {
            return new ArrayList<>();
        }

        int bestIndex = 0;
        double maxUtility = allAntPathUtilities.get(0);

        for (int i = 1; i < allAntPathUtilities.size(); i++) {
            if (allAntPathUtilities.get(i) > maxUtility) {
                maxUtility = allAntPathUtilities.get(i);
                bestIndex = i;
            }
        }

        return new ArrayList<>(allAntPaths.get(bestIndex));
    }

    /**
     * 更新任务执行次数和用户成本
     */
    private void updateTaskAndUserStatus(UserAlg user, List<TaskAlg> bestPath,
                                         Map<Long, TaskAlg> taskCacheMap,
                                         Set<Long> notIncreaseTaskIdSet) {
        double totalDistanceCost = 0;
        double totalExecutionCost = 0;

        // 计算路径总成本
        if (!bestPath.isEmpty()) {
            // 从起点到第一个任务的距离
            totalDistanceCost += calculateDistance(user.startX, user.startY,
                    bestPath.get(0).taskX, bestPath.get(0).taskY);

            // 任务间的距离
            for (int i = 1; i < bestPath.size(); i++) {
                totalDistanceCost += calculateDistance(bestPath.get(i-1).taskX, bestPath.get(i-1).taskY,
                        bestPath.get(i).taskX, bestPath.get(i).taskY);
            }

            // 从最后一个任务到终点的距离
            totalDistanceCost += calculateDistance(bestPath.get(bestPath.size()-1).taskX,
                    bestPath.get(bestPath.size()-1).taskY,
                    user.destX, user.destY);

            // 执行成本
            for (TaskAlg task : bestPath) {
                totalExecutionCost += task.executionCost;
            }
        }

        // 更新用户成本
        user.distanceCost = totalDistanceCost;
        user.executionCost = totalExecutionCost;
        user.usedCost = totalDistanceCost + totalExecutionCost;

        // 更新任务执行次数
        for (TaskAlg task : bestPath) {
            // 先计算质量增量，再更新执行次数k的值
            double deltaF = task.calDeltaFCommon();

            TaskAlg taskCache = taskCacheMap.get(task.id);
            if (taskCache == null) {
                taskCache = task;
                taskCacheMap.put(task.id, taskCache);
            }
            taskCache.k++;
            // 计算质量增量并更新总质量
            taskCache.totalF += deltaF;

            if (taskCache.totalF > 1) {
                log.info("任务[{}]的总质量大于1,totalF={},k={},successProb={}",
                        taskCache.id, taskCache.totalF, taskCache.k, taskCache.successProb);
                notIncreaseTaskIdSet.add(taskCache.id);
            }
        }
    }



    /**
     * 路径效用信息封装类
     */
    @Data
    private static class PathWithUtility {
        List<TaskAlg> path;
        double utility;
        int repeatCount;

        PathWithUtility(List<TaskAlg> path, double utility, int repeatCount) {
            this.path = path;
            this.utility = utility;
            this.repeatCount = repeatCount;
        }
    }
}